/**
 * //给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
 * //
 * // 你可以对一个单词进行如下三种操作：
 * //
 * //
 * // 插入一个字符
 * // 删除一个字符
 * // 替换一个字符
 * //
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：word1 = "horse", word2 = "ros"
 * //输出：3
 * //解释：
 * //horse -> rorse (将 'h' 替换为 'r')
 * //rorse -> rose (删除 'r')
 * //rose -> ros (删除 'e')
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：word1 = "intention", word2 = "execution"
 * //输出：5
 * //解释：
 * //intention -> inention (删除 't')
 * //inention -> enention (将 'i' 替换为 'e')
 * //enention -> exention (将 'n' 替换为 'x')
 * //exention -> exection (将 'n' 替换为 'c')
 * //exection -> execution (插入 'u')
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 0 <= word1.length, word2.length <= 500
 * // word1 和 word2 由小写英文字母组成
 * //
 * //
 * // Related Topics 字符串 动态规划 👍 2554 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00072EditDistance {
    public static void main(String[] args) {
        Solution solution = new ID00072EditDistance().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minDistance(String word1, String word2) {

            int m = word1.length();
            int n = word2.length();

            int[][] dp = new int[m + 1][n + 1];
            int a = 0;
            while (a <= m) {
                dp[a][0] = a;
                a++;
            }
            a = 0;
            while (a <= n) {
                dp[0][a] = a;
                a++;
            }

            for (int i = 1; i <= m; i++) {
                char w1 = word1.charAt(i - 1);
                for (int j = 1; j <= n; j++) {
                    char w2 = word2.charAt(j - 1);
                    int word1delete = dp[i - 1][j] + 1;
                    int word1add = dp[i][j - 1] + 1;
                    int word1Change = dp[i - 1][j - 1];

                    if (w1 != w2) {
                        word1Change += 1;

                    }
                    dp[i][j] = Math.min(word1delete, Math.min(word1add, word1Change));

                }
            }

            return dp[m][n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}